C++ program to find the GCD of two numbers

In this tutorial, we will write a c++ program to find the GCD of two numbers.

GCD (Greatest common divisor) is also known as HCF (Highest Common Factor).

For example

36 = 2 * 2 * 3 * 3

60 = 2 * 2 * 3 * 5

The highest common factor of the two numbers is 2, 2, and 3.

So, the HCF of two numbers is 2 * 2 * 3 = 12

20 = 2 * 2 * 5

28 = 2 * 2 * 7

The highest common factor of the two numbers is 2 and 2.

So, the HCF of two numbers is 2 * 2 = 4.

Approach 1

The problem can be solved by finding all the prime factors of the two numbers and then find common factors and return their product.

C++ code

Output

Approach 2

Approach 1 can be solved in an efficient way using the Euclidean algorithm. This algorithm follows the idea that GCD does not change if the smaller number gets subtracted from the larger one.

C++ code

Output

Approach 3

Approach two can be optimized further to use a modulo operator instead of subtraction.

C++ code

Output